1316. Одинаковые шары

Корабельная роща. 1898. При сравнении колорита «Корабельной рощи», позднего произведения Шишкина, с колоритом ранних его работ, ясно видно, что художник-пейзажист, подобно своим современникам-жанристам, перешел от локального понимания цвета к скупой, но целостной цветовой гамме. В основе этой гаммы лежит передача объединяющей изображение светотени.

В этой картине Шишкин нашел в цветовом объединении серовато-коричневых стволов елей и зелени мха на первом плане новое для себя тональное понимание цвета.

Картина интересна также новым способом передачи пространства леса. Деревья изображаются не целиком, а как бы срезаются рамой. Ели даются видимыми в непосредственной близости, но когда зритель смотрит на них, он не способен охватить всю картину в целом.

В непрозрачной закрытой урне с небольшим отверстием в крышке находится n шаров (n – четное число), половина из которых черные, а другая половина – белые. У Вас есть симметрическая монета, которую Вы начинаете подбрасывать.

· Если выпадает орел, Вы извлекаете белый шар;

· Если выпадает решка, Вы извлекаете черный шар;

Этот процесс продолжается до тех пор, пока в урне не останется ровно два шара. В этот момент они оказываются одинакового цвета, и дальнейшие подбрасывания монеты теряют смысл. До этого момента в урне всегда присутствует хотя бы один черный и хотя бы один белый шар.

Какова вероятность того, что произойдет описанная ситуация?

Вход. Каждая строка представляет собой отдельный тест и содержит одно четное число n (0 < n £ 10⁵) – количество шаров в урне.

Выход. Для каждого теста выведите в отдельной строке вероятность того, что произойдет описанная ситуация. Ответ должен быть выведен с точностью до восьми десятичных знаков.

Пример входа	Пример выхода
6 10 256	0.62500000 0.72656250 0.94998552

РЕШЕНИЕ

теория вероятности

Анализ алгоритма

Вычислим вероятность противоположного события X – того, что последними будут вынуты шары разного цвета. Для этого среди первых n – 2 вынутых шаров ровно половина должна быть белыми, а половина – черными.

Рассмотрим схему испытаний Бернулли, где вероятность успеха (например, появления белого шара) равна p = 1/2, а неуспеха q = 1 – p = 1/2. Вероятность того, что среди n – 2 вынутых шаров окажется ровно (n – 2) / 2 белых, вычисляется по формуле:

P(X) = =

Остается для каждого входного n вычислить значение P(X) и вывести 1 – P(X).

Хотя P(X) находится в пределах от 0 до 1 включительно, его непосредственное вычисление может привести к числовым проблемам. Чтобы избежать этого, вычислим логарифм:

ln P(X) = ln(n – 2)! – –

После вычисления правой части равенства возведем е в полученное значение, чтобы восстановить P(X). Логарифм факториала вычислим как сумму логарифмов:

ln n! = ln 1 + ln 2 + ln 3 + … + ln n

Так как на вход программы подаются несколько тестов, все ответы следует предвычислить и сохранить в массиве.

Пример

Для n = 6 вероятность того, что последними будут вынуты шары разного цвета, равна

= =

Вероятность того, что последними будут вынуты шары одного цвета, равна

1 – = = 0,625

Реализация алгоритма

Объявим необходимые массивы. В ячейке ans[i] будем хранить значение .

#define MAX 100001

double lf[MAX], ans[MAX];

Заполним массив lf, где lf[i] хранит значение ln i!.

res = lf[1] = 0.0;

for (res = 0, i = 2; i < MAX; i++)

{

res += log((double)i);

lf[i] = res;

}

Для каждого значения i вычислим и сохраним результат в ans[i].

for (i = 2; i < MAX; i += 2)

{

res = lf[i/2-1];

res = lf[i-2] - (i - 2) * log(2.0) – res - res;

ans[i] = exp(res);

}

Для каждого входного значения n вычисляем и выводим ответ.

while (scanf("%d",&n) == 1)

printf("%.8lf\n",1 - ans[n]);